package com.ly.algorithm.leetcode;
import java.util.Arrays;
import	java.util.HashMap;
import	java.util.Map;

/**
 * @Classname Problem75
 * @Description
 * 给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
 *
 * 此题中，我们使用整数 0、 1.txt 和 2 分别表示红色、白色和蓝色。
 *
 * 注意:
 * 不能使用代码库中的排序函数来解决这道题。
 *
 * 示例:
 *
 * 输入: [2,0,2,1.txt,1.txt,0]
 * 输出: [0,0,1.txt,1.txt,2,2]
 * 进阶：
 *
 * 一个直观的解决方案是使用计数排序的两趟扫描算法。
 * 首先，迭代计算出0、1.txt 和 2 元素的个数，然后按照0、1.txt、2的排序，重写当前数组。
 * 你能想出一个仅使用常数空间的一趟扫描算法吗？
 *
 * @Date 2020/10/7 20:02
 * @Author 冷心影翼
 */
public class Problem75 {

	public static void main(String[] args) {
		Solution75 solution75 = new Solution75();
		solution75.sortColors(new int[]{2,0,2,1,1,0});
		solution75.sortColorsBestWay(new int[]{2,0,2,1,1,0});
		solution75.sortColorsBestWay2(new int[]{2,0,2,1,1,0});
	}
}


class Solution75 {
	public void sortColors(int[] nums) {
		Map<Integer, Integer> map = new HashMap<> ();
		map.put(0,0);
		map.put(1,0);
		map.put(2,0);
		for(int n: nums) {
			map.put(n,map.get(n)+1);
		}
//		map.forEach((k,v)->System.out.println(k+":"+v));
		Arrays.fill(nums,0,map.get(0),0);
		Arrays.fill(nums,map.get(0),map.get(0)+map.get(1),1);
		Arrays.fill(nums,map.get(0)+map.get(1),map.get(0)+map.get(1)+map.get(2),2);
//		System.out.println(Arrays.toString(nums));
	}

	//使用双指针
	public void sortColorsBestWay(int[] nums) {
		int p0 = 0;
		int p2 = nums.length-1;
		for(int i=0;i<=p2;i++) {
			if(nums[i] == 0) {
				nums[i] = nums[p0];
				nums[p0++] = 0;
			}else if(nums[i] == 2) {
				nums[i--] = nums[p2];
				nums[p2--] = 2;
			}
		}
		System.out.println(Arrays.toString(nums));
	}
	//[2,0,2,1.txt,1.txt,0]
	public void sortColorsBestWay2(int[] nums) {
		int p0 = 0;
		int p2 = nums.length-1;
		for(int i=0;i<=p2;i++) {
			while (i<= p2 && nums[i] == 2) {
				int temp = nums[i];
				nums[i] = nums[p2];
				nums[p2] = temp;
				p2--;
			}
			if(nums[i] == 0) {
				int temp = nums[i];
				nums[i] = nums[p0];
				nums[p0] = temp;
				p0++;
			}
		}
		System.out.println(Arrays.toString(nums));
	}

}